package org.example.leetCode;

import java.util.Arrays;

/**
 * 221. 最大正方形
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 */
public class Code221 {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int result=0;
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - '0'; // 字符转数字
            result = Math.max(result, dp[i][0]);
        }

        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j] - '0'; // 字符转数字
            result = Math.max(result, dp[0][j]);
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]=='0'){
                    dp[i][j]=0;
                }else{
                    dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
                    result=Math.max(result,dp[i][j]);
                }
            }
        }
        return result*result;

    }
    public static void main(String[] args) {
        Code221 solution = new Code221();

        // 测试用例1: 4x5矩阵，最大正方形边长为2
        char[][] matrix1 = {
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}
        };
        int result1 = solution.maximalSquare(matrix1);
        System.out.println("测试用例1:");
        printMatrix(matrix1);
        System.out.println("最大正方形面积: " + result1);
        System.out.println("预期结果: 4 (边长为2的正方形)");
        System.out.println();

        // 测试用例2: 全0矩阵
        char[][] matrix2 = {
                {'0','0','0'},
                {'0','0','0'},
                {'0','0','0'}
        };
        int result2 = solution.maximalSquare(matrix2);
        System.out.println("测试用例2:");
        printMatrix(matrix2);
        System.out.println("最大正方形面积: " + result2);
        System.out.println("预期结果: 0");
        System.out.println();

        // 测试用例3: 全1矩阵
        char[][] matrix3 = {
                {'1','1'},
                {'1','1'}
        };
        int result3 = solution.maximalSquare(matrix3);
        System.out.println("测试用例3:");
        printMatrix(matrix3);
        System.out.println("最大正方形面积: " + result3);
        System.out.println("预期结果: 4 (边长为2的正方形)");
        System.out.println();

        // 测试用例4: 单个元素
        char[][] matrix4 = {{'1'}};
        int result4 = solution.maximalSquare(matrix4);
        System.out.println("测试用例4:");
        printMatrix(matrix4);
        System.out.println("最大正方形面积: " + result4);
        System.out.println("预期结果: 1 (边长为1的正方形)");
        System.out.println();

        // 测试用例5: 边长为3的正方形
        char[][] matrix5 = {
                {'1','1','1','0'},
                {'1','1','1','0'},
                {'1','1','1','1'},
                {'0','0','1','1'}
        };
        int result5 = solution.maximalSquare(matrix5);
        System.out.println("测试用例5:");
        printMatrix(matrix5);
        System.out.println("最大正方形面积: " + result5);
        System.out.println("预期结果: 9 (边长为3的正方形)");
    }

    // 辅助方法：打印矩阵
    private static void printMatrix(char[][] matrix) {
        for (char[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }
}
